# 合并(归并)排序法
# 递归方法, 和01的区别: merge不用返回值, 而是直接修改原列表的顺序
from utils.array_utils import sjlb
from utils.array_utils import check


def sort(array):
    if len(array) < 2:
        return array
    mid = len(array) // 2
    # 从中间分成左右两个列表
    left = array[:mid]
    right = array[mid:]
    sort(left)
    sort(right)
    len_left = len(left)
    len_right = len(right)
    # print(left, right)
    index_left = index_right = 0
    temp_list = []
    while index_left < len_left and index_right < len_right:
        # 将小的存到临时列表中
        if left[index_left] <= right[index_right]:
            temp_list.append(left[index_left])
            index_left += 1
        else:
            temp_list.append(right[index_right])
            index_right += 1
    # print(index_left,index_right)
    # 左表还有没遍历到的, 将左表剩余的放进临时表中
    while index_left < len_left:
        temp_list.append(left[index_left])
        index_left += 1
    while index_right < len_right:
        temp_list.append(right[index_right])
        index_right += 1

    # print('temp_list:', temp_list)
    for j, t in enumerate(temp_list):
        array[j] = t
    array = temp_list


if __name__ == '__main__':
    # l = sjlb()
    # # l = [7, 4, 1, 10, 6, 3, 7, 1, 0, 16,9]
    # print(l)
    # sort(l)

    for i in range(1000):
        l = sjlb()
        # print(l)
        sort(l)
        if not check(l):
            print('wrong: ', l)
        # print(l)
